题解 AT2164 【Rabbit Exercise】

发表于 | 更新于

有$n$只兔子在一个数轴上，兔子为了方便起见从$ 1 $到$n $标号，第$ i $只兔子的初始坐标为$x_i$。兔子会以以下的方式在数轴上锻炼：一轮包含$m$个跳跃，第 $j$ 个是兔子$a[j] (2 \leqslant a[j] \leqslant N−1)$，$a$是给出的长度为$m$的数组跳一下，这一下从 兔子$a[j]− 1 $和 兔子$a[j] + 1$中等概率的选一个$（$假设选了$ x）$，那么$a[j]$号兔子 会跳到它当前坐标关于$x$的坐标的对称点。（注意，即使兔子的位置顺序变化了，但是编号仍保持不变，这里按兔子编号算）兔子会进行$k$轮跳跃，对每个兔子，请你求出它最后坐标的期望值。

当$k=1$时，$a[i]=\frac{1}{2}[a[i-1]-(a[i]-a[i-1])]+\frac{1}{2}[a[i+1]+(a[i+1]-a[i])]$

经过化简后$a[i]=a[i+1]+a[i-1]-a[i]$,用差分数组表示就是:

$c[i]=a[i]-a[i-1]$

$c[i]=(a[i+1]+a[i-1]-a[i])-a[i-1]$

$c[i]=a[i+1]-a[i]$

$c[i]=c[i+1]$

$c[i+1]=a[i+1]-a[i]$

$c[i+1]=a[i+1]-(a[i+1]+a[i-1]-a[i])$

$c[i+1]=a[i]-a[i-1]$

$c[i+1]=c[i]$

然后我们发现一次运算就是把$c[i]$与$c[i+1]$交换，于是$k$轮跳转就相当于$k$次交换，然后利用类似快速幂的方法求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define int long long
#define re register
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int a[100007],c[100007],v[100007],t[100007],n;
inline void ksm(int p){
    while (p){
        if (p&1){
            for (int i=1;i<=n;++i)t[i]=c[v[i]];
            for (int i=1;i<=n;++i)c[i]=t[i];
        }
        for (int i=1;i<=n;++i)t[i]=v[v[i]];
        for (int i=1;i<=n;++i)v[i]=t[i];
        p>>=1;
    }
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read(),c[i]=a[i]-a[i-1],v[i]=i;
    int m=read(),k=read();
    for(int i=1;i<=m;i++){
        int x=read();
        swap(v[x],v[x+1]);
    }
    ksm(k);
    double sum=0;
    for (int i=1;i<=n;++i){
        sum+=c[i];
        printf("%.1lf\n",sum);
    }
    return 0;
}